/*
 * @Author: your name
 * @Date: 2024-04-06 16:43:47
 * @LastEditTime: 2024-04-08 20:52:06
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\151.反转字符串中的单词.cpp
 */
/*
 * @lc app=leetcode.cn id=151 lang=cpp
 *
 * [151] 反转字符串中的单词
 */

// @lc code=start
class Solution {
public:
    // 反转字符串s中左闭右闭的区间[start, end]
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    // 删除多余的空格
    void deleteExtraSpace(string& s){
        int slow = 0, fast = 0;
        for(fast = 0; fast < s.size(); fast++){
            if(s[fast] != ' '){
                // 去除所有空格
                if(slow != 0){
                    // 不是第一个单词，单词前需要添加空格
                    s[slow++] = ' ';
                }
                while(fast < s.size() && s[fast] != ' '){
                    s[slow++] = s[fast++];
                }

            }
        }
        s.resize(slow);
    }
    string reverseWords(string s) {
        deleteExtraSpace(s);
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for(int i = 0; i<=s.size(); ++i){
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};
// @lc code=end

